package hot

/*
*
312. 戳气球

有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。
这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
求所能获得硬币的最大数量。

示例 1：
输入：nums = [3,1,5,8]
输出：167
解释：
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167

示例 2：
输入：nums = [1,5]
输出：10

nums = [1,3,1,5,8,1]
dp 二维的 n*n 的矩阵
假设这个区间是个开区间, 最左边索引i, 最右边索引j
我这里说 "开区间"的意思是, 我们只能戳爆 i 和 j 之间的气球, i 和 j 不能戳
DP思路是这样的, 就是先别管前面是怎么戳的, 你只要管这个区间最后一个被戳破的是哪个气球
这最后一个被戳爆的气球就是k, k是这个区间, 最后要给 被戳爆的气球
因为是最后一个被戳爆的, 所以它周边没有球了, 只有这个开区间首位的 i 和 j 了
假设 dp[i][j] 表示开区间(i,j) 内你能拿到的最多金币
那么这个情况下:

	你在(i,j) 开区间得到的金币可以由 dp[i][k]和dp[k][j]进行转移
	如果你此可选择戳爆气球 k, 那么你得到的金币数量就是: total = dp[i][k] + val[i]*val[k]*val[j] + dp[k][j]
	val[i]表示 i位置气球的数字, (i,k)和(k,j) 也都是开区间
	所以(i,j) 区间中 k 两边的东西必然是先各自被戳爆了的, 左右两边互不干扰
	这就是为什么我们 DP时要看"最后一个被戳爆的" 气球, 这就是为了让左右两边互不干扰, 一种分治的思想

而你在(i,j) 开区间可以选的k是有多个的, 枚举一下这几个k, 从中选择使得 total值最大的即可用来更新 dp[i][j]
开区间的长度从3个开始, 一直到len(nums) 所以下标n从2到len(nums)-1
每个dp从0到n 进行最大值转移

	0	2
	1	3
	2	4
	3	5
	0	3
	1	4

你就从(i,j) 开区间只有三个数字的时候开始计算, 存储每个小区间可以得到金币的最大值, 然后慢慢扩展到更大的区间
最终返回的是dp[0][len(nums) - 1]
*/
func maxCoins(nums []int) int {

	//1.获取切片长度
	n := len(nums)

	//2.创建新二维数组,长度+2,
	dp := make([][]int, n+2)
	for i := 0; i < n+2; i++ {
		dp[i] = make([]int, n+2)
	}

	//3.将参数数组, 转化为新数组(左右两边添加一个1)
	newArr := make([]int, n+2)
	newArr[0], newArr[n+1] = 1, 1
	for i := 1; i <= n; i++ {
		newArr[i] = nums[i-1]
	}

	//4.进行dp填充
	for i := n - 1; i >= 0; i-- { //从最后一个下标开找
		for j := i + 2; j <= n+1; j++ { // 以i+2为右端点, 不断增加到n+1
			for k := i + 1; k < j; k++ { //k取值i+1,因为i不被戳爆, k<j

				//计算选择k位置时的sum
				sum := newArr[i] * newArr[k] * newArr[j]
				//sum = dp[i][k] + sum + dp[k][j]
				sum += dp[i][k] + dp[k][j]

				//更新dp[i][j]的值
				dp[i][j] = max(dp[i][j], sum)
			}
		}
	}

	//5.返回最终结果
	return dp[0][n+1]
}
